今天是紀錄LeetCode解題的第四十二天
是一題困難題

第四十二題題目：

給定n個非負整數表示高程圖，其中每個長條圖的寬度為1，計算下雨後該高程圖可以容納多少水

解題思路

這題用雙指針的概念，一樣有left、right從兩邊開始掃描，然後還需要left_max和right_max來儲存掃描過程中最大的高度，接著判斷height[l]、height[r]誰大誰小，由小的高度去做移動，如果目前height[l] (或height[r])大於等於left_max(或right_max)則把left_max(或right_max)=height[l] (或height[r])，如果當前指針指的高度沒有比最大值大，那麼就用最大值減掉當前指針指的高度算出雨水(由低的地方到高的地方不會累積雨水，但從高的地方到低的地方，例如從高度2到高度1，則會累積一格雨水)

程式碼

class Solution:
    def trap(self, height: List[int]) -> int:
        l,r = 0,len(height) - 1
        left_max,right_max = 0,0
        water = 0
        while l < r:
            if height[l] < height[r]:
                if height[l] >= left_max:
                    left_max = height[l]
                else:
                    water += left_max - height[l]
                l += 1
            else:
                if height[r] >= right_max:
                    right_max = height[r]
                else:
                    water += right_max - height[r]
                r -= 1
        return water

執行過程

初始狀態

• height = [4,2,0,3,2,5]
• l,r = 0,5
• left_max,right_max = 0,0
• water = 0

第一次執行

• if height[l] < height[r] → 4 < 5 → True
• if height[l] >= left_max → 4 >= 0 → True
• left_max = height[l] = 4
• l += 1 = 1

第二次執行

• if height[l] < height[r] → 2 < 5 → True
• if height[l] >= left_max → 2 >= 4 → False
• water += left_max - height[l] → water = 0 + 4 - 2 = 2
• l += 1 = 2

第三次執行

• if height[l] < height[r] → 0 < 5 → True
• if height[l] >= left_max → 0 >= 4 → False
• water += left_max - height[l] → water = 2 + 4 - 0 = 6
• l += 1 = 3

第四次執行

• if height[l] < height[r] → 3 < 5 → True
• if height[l] >= left_max → 3 >= 4 → False
• water += left_max - height[l] → water = 6 + 4 - 3 = 7
• l += 1 = 4

第五次執行

• if height[l] < height[r] → 2 < 5 → True
• if height[l] >= left_max → 2 >= 4 → False
• water += left_max - height[l] → water = 7 + 4 - 2 = 9
• l += 1 = 5

最後回傳答案9